[38;2;117;113;94m#[0m[38;2;117;113;94m quicksort.awk --- Quicksort algorithm, with user-supplied[0m
[38;2;117;113;94m#[0m[38;2;117;113;94m                   comparison function[0m
[38;2;117;113;94m#[0m
[38;2;117;113;94m#[0m[38;2;117;113;94m Arnold Robbins, arnold@skeeve.com, Public Domain[0m
[38;2;117;113;94m#[0m[38;2;117;113;94m January 2009[0m


[38;2;117;113;94m#[0m[38;2;117;113;94m quicksort --- C.A.R. Hoare's quicksort algorithm. See Wikipedia[0m
[38;2;117;113;94m#[0m[38;2;117;113;94m               or almost any algorithms or computer science text.[0m
[38;2;117;113;94m#[0m
[38;2;117;113;94m#[0m[38;2;117;113;94m Adapted from K&R-II, page 110[0m

[3;38;2;102;217;239mfunction[0m[38;2;248;248;242m [0m[38;2;166;226;46mquicksort[0m[38;2;248;248;242m([0m[3;38;2;253;151;31mdata[0m[38;2;248;248;242m, [0m[3;38;2;253;151;31mleft[0m[38;2;248;248;242m, [0m[3;38;2;253;151;31mright[0m[38;2;248;248;242m, [0m[3;38;2;253;151;31mless_than[0m[38;2;248;248;242m,    [0m[3;38;2;253;151;31mi[0m[38;2;248;248;242m, [0m[3;38;2;253;151;31mlast[0m[38;2;248;248;242m)[0m
[38;2;248;248;242m{[0m
[38;2;248;248;242m    [0m[38;2;249;38;114mif[0m[38;2;248;248;242m [0m[38;2;255;255;255m([0m[38;2;255;255;255mleft[0m[38;2;248;248;242m [0m[38;2;249;38;114m>=[0m[38;2;248;248;242m [0m[38;2;255;255;255mright[0m[38;2;255;255;255m)[0m[38;2;248;248;242m  [0m[38;2;117;113;94m#[0m[38;2;117;113;94m do nothing if array contains fewer[0m
[38;2;248;248;242m        [0m[38;2;255;255;255mreturn[0m[38;2;248;248;242m          [0m[38;2;117;113;94m#[0m[38;2;117;113;94m than two elements[0m

[38;2;248;248;242m    [0m[38;2;166;226;46mquicksort_swap[0m[38;2;255;255;255m([0m[38;2;255;255;255mdata[0m[38;2;248;248;242m,[0m[38;2;248;248;242m [0m[38;2;255;255;255mleft[0m[38;2;248;248;242m,[0m[38;2;248;248;242m [0m[38;2;102;217;239mint[0m[38;2;255;255;255m([0m[38;2;255;255;255m([0m[38;2;255;255;255mleft[0m[38;2;248;248;242m [0m[38;2;249;38;114m+[0m[38;2;248;248;242m [0m[38;2;255;255;255mright[0m[38;2;255;255;255m)[0m[38;2;248;248;242m [0m[38;2;249;38;114m/[0m[38;2;248;248;242m [0m[38;2;190;132;255m2[0m[38;2;255;255;255m)[0m[38;2;255;255;255m)[0m
[38;2;248;248;242m    [0m[38;2;255;255;255mlast[0m[38;2;248;248;242m [0m[38;2;249;38;114m=[0m[38;2;248;248;242m [0m[38;2;255;255;255mleft[0m
[38;2;248;248;242m    [0m[38;2;166;226;46mfor[0m[38;2;248;248;242m [0m[38;2;255;255;255m([0m[38;2;255;255;255mi[0m[38;2;248;248;242m [0m[38;2;249;38;114m=[0m[38;2;248;248;242m [0m[38;2;255;255;255mleft[0m[38;2;248;248;242m [0m[38;2;249;38;114m+[0m[38;2;248;248;242m [0m[38;2;190;132;255m1[0m[38;2;248;248;242m; [0m[38;2;255;255;255mi[0m[38;2;248;248;242m [0m[38;2;249;38;114m<=[0m[38;2;248;248;242m [0m[38;2;255;255;255mright[0m[38;2;248;248;242m; [0m[38;2;255;255;255mi[0m[38;2;249;38;114m++[0m[38;2;255;255;255m)[0m
[38;2;248;248;242m        [0m[38;2;166;226;46mif[0m[38;2;248;248;242m [0m[38;2;255;255;255m([0m[38;2;248;248;242m@[0m[38;2;166;226;46mless_than[0m[38;2;255;255;255m([0m[38;2;255;255;255mdata[0m[38;2;249;38;114m[[0m[38;2;255;255;255mi[0m[38;2;249;38;114m][0m[38;2;248;248;242m,[0m[38;2;248;248;242m [0m[38;2;255;255;255mdata[0m[38;2;249;38;114m[[0m[38;2;255;255;255mleft[0m[38;2;249;38;114m][0m[38;2;255;255;255m)[0m[38;2;255;255;255m)[0m
[38;2;248;248;242m            [0m[38;2;166;226;46mquicksort_swap[0m[38;2;255;255;255m([0m[38;2;255;255;255mdata[0m[38;2;248;248;242m,[0m[38;2;248;248;242m [0m[38;2;249;38;114m+[0m[38;2;249;38;114m+[0m[38;2;255;255;255mlast[0m[38;2;248;248;242m,[0m[38;2;248;248;242m [0m[38;2;255;255;255mi[0m[38;2;255;255;255m)[0m
[38;2;248;248;242m    [0m[38;2;166;226;46mquicksort_swap[0m[38;2;255;255;255m([0m[38;2;255;255;255mdata[0m[38;2;248;248;242m,[0m[38;2;248;248;242m [0m[38;2;255;255;255mleft[0m[38;2;248;248;242m,[0m[38;2;248;248;242m [0m[38;2;255;255;255mlast[0m[38;2;255;255;255m)[0m
[38;2;248;248;242m    [0m[38;2;166;226;46mquicksort[0m[38;2;255;255;255m([0m[38;2;255;255;255mdata[0m[38;2;248;248;242m,[0m[38;2;248;248;242m [0m[38;2;255;255;255mleft[0m[38;2;248;248;242m,[0m[38;2;248;248;242m [0m[38;2;255;255;255mlast[0m[38;2;248;248;242m [0m[38;2;249;38;114m-[0m[38;2;248;248;242m [0m[38;2;190;132;255m1[0m[38;2;248;248;242m,[0m[38;2;248;248;242m [0m[38;2;255;255;255mless_than[0m[38;2;255;255;255m)[0m
[38;2;248;248;242m    [0m[38;2;166;226;46mquicksort[0m[38;2;255;255;255m([0m[38;2;255;255;255mdata[0m[38;2;248;248;242m,[0m[38;2;248;248;242m [0m[38;2;255;255;255mlast[0m[38;2;248;248;242m [0m[38;2;249;38;114m+[0m[38;2;248;248;242m [0m[38;2;190;132;255m1[0m[38;2;248;248;242m,[0m[38;2;248;248;242m [0m[38;2;255;255;255mright[0m[38;2;248;248;242m,[0m[38;2;248;248;242m [0m[38;2;255;255;255mless_than[0m[38;2;255;255;255m)[0m
[38;2;248;248;242m}[0m

[38;2;117;113;94m#[0m[38;2;117;113;94m quicksort_swap --- helper function for quicksort, should really be inline[0m

[3;38;2;102;217;239mfunction[0m[38;2;248;248;242m [0m[38;2;166;226;46mquicksort_swap[0m[38;2;248;248;242m([0m[3;38;2;253;151;31mdata[0m[38;2;248;248;242m, [0m[3;38;2;253;151;31mi[0m[38;2;248;248;242m, [0m[3;38;2;253;151;31mj[0m[38;2;248;248;242m,      [0m[3;38;2;253;151;31mtemp[0m[38;2;248;248;242m)[0m
[38;2;248;248;242m{[0m
[38;2;248;248;242m    [0m[38;2;255;255;255mtemp[0m[38;2;248;248;242m [0m[38;2;249;38;114m=[0m[38;2;248;248;242m [0m[38;2;255;255;255mdata[0m[38;2;249;38;114m[[0m[38;2;255;255;255mi[0m[38;2;249;38;114m][0m
[38;2;248;248;242m    [0m[38;2;255;255;255mdata[0m[38;2;249;38;114m[[0m[38;2;255;255;255mi[0m[38;2;249;38;114m][0m[38;2;248;248;242m [0m[38;2;249;38;114m=[0m[38;2;248;248;242m [0m[38;2;255;255;255mdata[0m[38;2;249;38;114m[[0m[38;2;255;255;255mj[0m[38;2;249;38;114m][0m
[38;2;248;248;242m    [0m[38;2;255;255;255mdata[0m[38;2;249;38;114m[[0m[38;2;255;255;255mj[0m[38;2;249;38;114m][0m[38;2;248;248;242m [0m[38;2;249;38;114m=[0m[38;2;248;248;242m [0m[38;2;255;255;255mtemp[0m
[38;2;248;248;242m}[0m
